/* Copyright 2011 Tobias Marschall, Email: tm@cwi.nl 
 * 
 * This file is part of string-cover.
 *
 * string-cover is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * string-cover is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with string-cover.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <limits>

#include <boost/program_options.hpp>

#include "ProblemInstance.h"
#include "SimpleBoundProvider.h"
#include "LagrangianBoundProvider.h"
#include "BranchAndBoundSolver.h"
#include "BranchingRule.h"
#include "Solution.h"
#include "LengthBasedWeightFunction.h"
#include "StringBasedWeightFunction.h"

using namespace std;
namespace po = boost::program_options;

void usage(const char* name, const po::options_description& options_desc) {
	cerr << "Usage: " << name << " [options] <filename>" << endl;
	cerr << endl;
	cerr << options_desc << endl;
	exit(1);
}

string cleanString(string s) {
	ostringstream oss;
	for (size_t i=0; i<s.length(); ++i) {
		if (s[i]<32) continue;
		oss << s[i];
	}
	return oss.str();
}

vector<string>* readFile(string filename) {
	vector<string>* strings = new vector<string>();
	ifstream f;
	f.open(filename.c_str());
	if (!f.is_open()) {
		cerr << "Unable to open file \"" << filename << "\"." << endl;
		exit(1);
	}
	while(!f.eof()) {
		string s;
		getline(f, s);
		if (s.empty()) continue;
		//  cout << '"' << s << '"' << endl;
		strings->push_back(cleanString(s));
	}
	f.close();
	return strings;
}

int main(int argc, char* argv[]) {
	// PARAMETERS
	int status_iterations;
	double initial_mu;
	/** Number of non-improving iterations after which the step size is decreased. */
	int allowed_nonimproving_iterations;
	int allowed_nonimproving_iterations_root;
	/** Factor by which mu is decreased. */
	double mu_decrease_factor;
	/** When mu drops below this threshold, we terminate. */
	double mu_threshold;
	double mu_threshold_root;
	string weight_by_length_filename;
	string weight_by_string_filename;
	double default_weight;
	int min_length;
	int max_length;

	po::options_description options_desc("Allowed options");
	options_desc.add_options()
		("verbose,v", "Be verbose (implies \"-i 1\").")
	    ("no-subgradient,B", "Disable subgradient optimization and only use branch and bound.")
	    ("print-iteration,i", po::value<int>(&status_iterations)->default_value(100), "Number of iterations after which a status message is printed.")
	    ("initial_mu,u", po::value<double>(&initial_mu)->default_value(2), "Initial step size parameter for subgradient optimization.")
	    ("max-nonimproving,n", po::value<int>(&allowed_nonimproving_iterations)->default_value(5), "Maximal number of consecutive non-improving iterations until mu is decreased.")
	    ("max-nonimproving-root,N", po::value<int>(&allowed_nonimproving_iterations_root)->default_value(30), "Maximal number of consecutive non-improving iterations until mu is decreased in the root node.")
	    ("mu_decrease,d", po::value<double>(&mu_decrease_factor)->default_value(0.5), "Factor by which mu is decreased.")
	    ("mu_threshold,t", po::value<double>(&mu_threshold)->default_value(0.125), "When mu drops below this threshold, then branch (if necessary).")
	    ("mu_threshold_root,T", po::value<double>(&mu_threshold_root)->default_value(0.001), "mu threshold for the root node.")
	    ("weight_by_length,L", po::value<string>(&weight_by_length_filename)->default_value(""), "Reads weight function from given filename. Format: a pair \"<length> <weight>\" in each row. Default: use uniform weights.")
	    ("weight_by_string,S", po::value<string>(&weight_by_string_filename)->default_value(""), "Reads weight function from given filename. Format: a pair \"<string> <weight>\" in each row. Default: use uniform weights.")
	    ("default_weight,w", po::value<double>(&default_weight)->default_value(1000.0), "Weight used for strings not covered by given weight table (see options -L and -S).")
	    ("min_length,m", po::value<int>(&min_length)->default_value(-1), "Minimal length of used strings, default: no limit (-1).")
	    ("max_length,M", po::value<int>(&max_length)->default_value(-1), "Maximal length of used strings, default: no limit (-1).")
	    ("solution_branch_order,o", "Process branching nodes by their feasible solution score. (Default: by lower bound).")
	;

	if (argc<2) usage(argv[0], options_desc);
	string filename(argv[argc-1]);

	po::variables_map options;
	try {
		po::store(po::parse_command_line(argc-1, argv, options_desc), options);
		po::notify(options);
	} catch(exception& e) {
        cerr << "error: " << e.what() << "\n";
        return 1;
    }
	if ((weight_by_length_filename.length()>0) && (weight_by_string_filename.length()>0)) {
		cerr << "Error: options -L and -S are mutually exclusive." << endl;
		exit(1);
	}
	if (options.count("verbose")) {
		status_iterations = 1;
	}
#ifdef DEBUG
	status_iterations = 1;
#endif
	auto_ptr<vector<string> > strings(readFile(filename));
	cout << "Read " << strings->size() << " strings" << endl;

	ProblemInstance instance(strings);
	cout << "Intervals: " << instance.getIntervalNumbering().size() << endl;
	cout << "Different substrings: " << instance.getSubstrings().size() << endl;
	if (weight_by_length_filename.length()>0) {
		ifstream f;
		f.open(weight_by_length_filename.c_str());
		if (!f.is_open()) {
			cerr << "Unable to open file \"" << weight_by_length_filename << "\"." << endl;
			exit(1);
		}
		LengthBasedWeightFunction w(f, default_weight);
		instance.cacheWeights(w);
	}
	if (weight_by_string_filename.length()>0) {
		ifstream f;
		f.open(weight_by_string_filename.c_str());
		if (!f.is_open()) {
			cerr << "Unable to open file \"" << weight_by_string_filename << "\"." << endl;
			exit(1);
		}
		StringBasedWeightFunction w(f, default_weight);
		instance.cacheWeights(w);
	}
	Multipliers multipliers(instance);
	BoundProvider* bound_provider;
	if (options.count("no-subgradient")) {
		bound_provider = new SimpleBoundProvider(multipliers);
		cout << "Using pure branch and bound (no subgradient optimization)." << endl;
	} else {
		LagrangianBoundProvider* lbp = new LagrangianBoundProvider(multipliers);
		lbp->setVerbose(options.count("verbose"));
		lbp->setParameters(initial_mu, allowed_nonimproving_iterations, allowed_nonimproving_iterations_root, mu_decrease_factor, mu_threshold, mu_threshold_root);
		bound_provider = lbp;
	}
	branching_rule_t branching_strategy = LOWER_BOUND;
	if (options.count("solution_branch_order")) {
		branching_strategy = BEST_SOLUTION;
	}
	BranchingRule<BranchAndBoundSolver::node_queue_t> branching_rule(instance,branching_strategy);
	BranchAndBoundSolver solver(*bound_provider, branching_rule);
	solver.setMinLength(min_length);
	solver.setMaxLength(max_length);
	solver.setStatusIterations(status_iterations);

	auto_ptr<Solution> solution = solver.solve(instance);
	if (solution.get()!=0) {
		cout << "Optimal solution (score "<< solution->getScore() << "):" << endl;
		cout << *solution << endl;
		cout << "Factorization:" << endl;
		solution->printFactorizations(cout);
	} else {
		cout << "No feasible solution exists." << endl;
	}

	delete bound_provider;
	return 0;
}
